1. Field of the Invention
The present invention relates to a picture search technique for detecting a list of pictures similar to an inputted picture from a large-scale picture archive.
2. Background Art
The spread of digital archiving of TV pictures and moving picture distribution services on the Internet is increasing the need to search in and classify large-scale data at high speed. In particular, there is a need for a picture search technique using an image feature due to the difficulty in manually adding text information to a vast amount of picture content. Since a large-scale picture archive includes the same or similar pictures in large numbers, it is desirable to detect the pictures at high speed as thoroughly as possible. If the picture archive includes pictures whose playback speeds are different, such as a slow-motion picture and a fast-forward picture, detection of the pictures as similar pictures is also desired.
As a still image search method using an image feature, there is proposed a method including performing a search by extracting pieces of information such as color information and shape information of an image itself as pieces of higher dimensional vector information and evaluating the similarity between images on the basis of distances among vectors. A method including implementing a high-speed similarity search even in large-scale image data by clustering pieces of feature quantity data by k-means or the like and holding the clustered pieces is also known.
Known examples of a conventional similar picture search method using an image feature include a method using frame-by-frame feature quantity comparison between a query picture and a candidate for similar pictures. A general procedure of such a conventional method is to 1) capture each frame from a query picture and calculate an image feature quantity, 2) search for a frame whose feature quantity is close to a feature quantity of a leading frame of the query picture in a feature quantity database and set the frame as a candidate, 3) calculate the distances between the feature quantities of subsequent frames of the query picture and feature quantities of frames subsequent to each candidate, and 4) output, as a similar picture, a candidate in which the total value of feature quantity distances for a fixed number of frames or more is not more than a threshold value.
For example, in JP 2009-22018A, an inputted picture is divided into segments, in each of which variation in feature quantity between frames is within a specific range, a feature quantity extracted from a representative frame of each segment is stored in a feature quantity table, a frame similar to a new frame is searched for in the feature quantity table when the new frame is inputted, and all frames meeting conditions are set as candidates for similar frames. When a frame subsequent to the new frame is inputted, whether a feature quantity of the frame coincides with a feature quantity of a frame subsequent to each candidate is checked, and a candidate which coincides in feature quantity with the new frame for a length not less than a threshold value is outputted as a similar picture.
K. Yoshida and N. Murabayashi, “Tiny LSH for Content-based Copied Video Detection,” Proc. of SAINT 2008, IEEE CS, 2008 (hereinafter referred to as Non-Patent Document 1) discloses a method for speeding up selection of a candidate from a feature quantity table using a hash table. In this method, a plurality of hash values are calculated for each frame feature quantity by using a plurality of hash functions. The hash functions to be used each generate, from a feature quantity similar to a certain feature quantity, the same hash value as that of the latter feature quantity. A hash table in which a hash value is paired with a pointer to a feature quantity table is created. A pointer to a frame with a similar feature quantity can be obtained by calculating hash values and searching in the hash table when a new frame is inputted. Although hash value collision causes a pointer corresponding to a hash value in question to be overwritten, if there is a pointer paired with any of hash values other than the hash value, a similar frame can be found from the feature quantity table. Since such a candidate selection method adopts an algorithm using a hash table, the complexity of the method is constant regardless of the amount of data.
JP 2000-339474A discloses a method for calculating an accurate similarity in comparing feature quantities of moving images with different frame rates. This method uses means for correcting a frame position at which feature quantity comparison is to be performed while referring to the time position information of a query picture and the time position information of a segment of a picture to be searched for which is included in a database. Since a feature quantity comparison position is determined by using playback position information of a known moving image, a similar picture with a different frame rate can be detected.